import java.util.Arrays;

public class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length, minSuff = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > minSuff) {
                return false;
            }
            minSuff = Math.min(minSuff, nums[i + 1]);
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] testCases = {
                {0, 1, 2},      // true - 已排序
                {1, 0, 2},      // true - 只有局部逆序
                {1, 2, 0},      // false - 存在全局逆序
                {2, 0, 1},      // false - 存在全局逆序
                {2, 1, 0},      // false - 多个逆序
                {0, 2, 1},      // true - 只有局部逆序
                {0},            // true - 单个元素
                {0, 1},         // true - 两个元素顺序
                {1, 0}          // true - 两个元素逆序
        };

        boolean[] expectedResults = {
                true, true, false, false, false, true, true, true, true
        };

        System.out.println("测试理想排列判断:\n");
        for (int i = 0; i < testCases.length; i++) {
            int[] nums = testCases[i];
            boolean result = solution.isIdealPermutation(nums);
            boolean expected = expectedResults[i];
            String status = result == expected ? "✓ 通过" : "✗ 失败";

            System.out.printf("测试 %d: %s\n", i + 1, status);
            System.out.printf("输入: %s\n", Arrays.toString(nums));
            System.out.printf("结果: %b, 期望: %b\n\n", result, expected);
        }

        // 额外性能测试（大数组）
        System.out.println("性能测试 (n=10000):");
        int[] largeArray = new int[10000];
        for (int i = 0; i < largeArray.length; i++) {
            largeArray[i] = i;
        }
        // 交换相邻元素创建局部逆序
        largeArray[5000] = 5001;
        largeArray[5001] = 5000;

        long startTime = System.nanoTime();
        boolean result = solution.isIdealPermutation(largeArray);
        long endTime = System.nanoTime();

        System.out.printf("结果: %b (耗时: %.3f ms)\n", result, (endTime - startTime) / 1_000_000.0);
    }
}